package sort;

public class CountingSort {

    /**
     * counting sort
     * @param A input list, raw data
     * @param B output sorted list
     * @param k A[i] ∈ [0, k] and k ∈ Z, i=0,1,2,...,A.length-1
     */
    public static void cSort(int[] A, int[] B, int k) {
        if (k <= 0) return;

        int[] c = new int[k + 1]; // counting array, c[0..k] stores count(A[0..length-1])

        // init counting array c[]
        for (int i = 0; i < c.length; i++) {
            c[i] = 0;
        }

        // set c[i] = count(x == A[j]), i = A[j]
        for (int j = 0; j < A.length; j++) {
            c[A[j]] ++;
        }

        // set c[i] = count(x <= A[j]), i = A[j]
        for (int i = 1; i < c.length; i++) {
            c[i] = c[i-1] + c[i];
        }

        // now, we know element i (i = A[j]) should be located in index c[i] of B
        // Provided that count(i) > 1, let j vary from A.length-1 to 0 to ensure a stable sorting
        for (int j = A.length-1; j >= 0 ; j--) {
            B[c[A[j]] - 1] = A[j]; // B[0..length-1] stores sorted result of A[0..length-1], and location should exclude count value of itself.
//            B[c[A[j]]] = A[j];
            c[A[j]] --;
        }

    }

    /**
     * interface of counting sort, sort A[p..r]
     * @param A input list, raw data
     * @param p first element's location
     * @param r last element's location
     */
    public static void countingSort(int[] A, int p, int r) {
        int max = A[p];
        int min = A[p];

        for (int i = p+1; i < r; i++) {
            if (max < A[i]) max = A[i];
            if (min > A[i]) min = A[i];
        }

        int[] B = new int[A.length];
        cSort(A, B, max);

        // copy sorted B[0..length-1] to A[0..length-1]
        for (int i = 0; i < A.length; i++) {
            A[i] = B[i];
        }
    }
}
